package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-09-11 19:46
 */

import java.util.HashMap;

/**
 * 题目：
 * 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，
 * 并返回该子数组的长度。
 */

//暴力破解 但是时间复杂度过大 无法处理大数组
public class Test23_0和1个数相同的子数组 {
    public int findMaxLength1(int[] nums) {
        int len = 0;
        for (int i = 0; i < nums.length; i++) {
            int a = 0;
            int b = 0;
            for (int j = i; j < nums.length; j++) {
                if (nums[j] == 1) {
                    a += 1;
                }
                if (nums[j] == 0) {
                    b += 1;
                }
                if (a == b) {
                    len = Math.max(len, 2 * a);
                }
            }
        }
        return len;
    }

    public int findMaxLength(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int pre_sum = 0;
        int ret = 0;
        for (int i = 0; i < nums.length; i++) {
            pre_sum += nums[i] == 0 ? -1 : 1;
            if (map.containsKey(pre_sum)) {
                ret = Math.max(ret, i - map.get(pre_sum));
            } else {
                map.put(pre_sum, i);
            }
        }

        return ret;
    }

}
